#include <stdlib.h>
//#include <random.h>
#include <iostream>
#define MAXLevel 16
class ListNode
{
public:
    int value;
    ListNode * forward[MAXLevel] ={0};
    /*
    level 0 原始列表
    level 1 一级列表
    以此类推
    */
    ListNode(int v):value(v){}
};

class SkipList
{
public:
    ListNode *header;
public:
    SkipList()
    {
        header = new ListNode(0);
        
    }

    bool search(int target)
    {
        ListNode * currLevelNode = header; //当前层对应的起始搜索点
        ListNode * tempnode;
        for(int level = MAXLevel-1;level >=0;level --)
        {
            while(currLevelNode ) //当前层对应的起始搜索点 (并未搜索到的节点)
            {
                if((tempnode = currLevelNode->forward[level])!=NULL) //当前层对应的起始搜索点 的前一个节点
                {
                    if(target==tempnode->value)
                    {
                        return true;
                    }
                    else if(target > tempnode->value)
                    {
                        currLevelNode = tempnode ;
                    }
                    else
                    {
                        break;
                    }
                    
                }
                else
                {
                    break;
                }
            }
        }
        return false;
    }

    void add(int num)
    {
        ListNode * newNode  = new ListNode(num);
        int newNode_Level = getRandomLevel();

        //在搜索的基础上 添加节点
        ListNode * currLevelNode = header; //当前层对应的起始搜索点
        ListNode * tempnode = NULL;

        for(int level = MAXLevel-1;level >=0;level --)
        {
            while(currLevelNode ) //当前层对应的起始搜索点 (并未搜索到的节点)
            {
                if(currLevelNode->forward[level]!=NULL) //当前层对应的起始搜索点 的后一个节点
                {
                    tempnode = currLevelNode->forward[level];
                    if(num > tempnode->value)
                    {
                        currLevelNode = tempnode ;
                    }
                    if(num <= tempnode->value)  //此时进入下一层搜索(支持插入重复节点,新节点插入重复节点的前一个)
                    {
                        if(level <= newNode_Level)
                        {
                            currLevelNode->forward[level] = newNode;
                            newNode->forward[level]= tempnode;
                        }
                        break;
                    } 
                }
                else if(level <= newNode_Level)
                {
                    currLevelNode->forward[level] = newNode;
 
                    break;
                }
                else
                {
                    break;
                }  
            }
        }
    }

    bool erase(int num) 
    {
        ListNode * targetNode  = NULL;  //随机删除节点
        bool isFind = false; //需要删除的随机节点 有没有找到
        
        ListNode * currLevelNode = header; //当前层对应的起始搜索点
        ListNode * tempnode = NULL;

        for(int level = MAXLevel-1;level >=0;level --)
        {
            while(currLevelNode ) //当前层对应的起始搜索点 (并未搜索到的节点)
            {
                if(currLevelNode->forward[level]!=NULL) //当前层对应的起始搜索点 的后一个节点
                {
                    tempnode = currLevelNode->forward[level];
                    if(num == tempnode -> value )
                    {
                        if(!isFind) //未找到,则设立
                        {
                            isFind = true;
                            targetNode = tempnode;
                            currLevelNode->forward[level] = tempnode->forward[level];
                            break;
                        }
                        else  //已找到,则需要判断 tempnode 与 targetNode 是否是同一个节点
                        {
                            if(targetNode == tempnode)
                            {
                                currLevelNode->forward[level] = tempnode->forward[level];
                                break;
                            }
                            else
                            {
                                currLevelNode = tempnode;
                            }
                        }
                        
                    }
                    if(num > tempnode->value)
                    {
                        currLevelNode = tempnode ;
                    }
                    if(num < tempnode->value)  //此时进入下一层搜索(支持插入重复节点,新节点插入重复节点的前一个)
                    {
                        break;
                    } 
                }
                else
                {
                    break;
                }  
            }
        }
        return isFind;
    }

    int getRandomLevel()
    {
        int level = 0;
        for(int i=0;i<MAXLevel;i++)
        {
            if((rand() %100)<50)
            {
                level ++;
            }
            else
            {
                return level;
            }
            
        }
        return level;
    }

};
int main()
{
    SkipList sp;
    // for(int i=0;i<10000;i++)
    // {
    //     //std::cout<<rand()<<" ";
    //     std::cout<<sp.getRandomLevel()<<" ";
    // }
    sp.add(3);
    sp.add(1);
    sp.add(9);
    sp.add(7);
    sp.add(11);
    sp.add(11);
    sp.add(17);
    sp.add(25);
    sp.erase(11);
    std::cout<<sp.search(2)<<std::endl;
    std::cout<<sp.search(3)<<std::endl;
    std::cout<<sp.search(1)<<std::endl;
    std::cout<<sp.search(9)<<std::endl;
    std::cout<<sp.search(0)<<std::endl;
    std::cout<<sp.search(11)<<std::endl;
    ListNode * node = sp.header->forward[0];
    std::cout<<"level 0"<<std::endl;
    while (node)
    {
        std::cout<<"node="<<node->value<<std::endl;
        node = node->forward[0];
    }
    std::cout<<"level 1 "<<std::endl;
    ListNode * node2 = sp.header->forward[1];
    while (node2)
    {
        std::cout<<"node="<<node2->value<<std::endl;
        node2 = node2->forward[1];
    }


    std::cout<<"level 2 "<<std::endl;
      node2 = sp.header->forward[2];
    while (node2)
    {
        std::cout<<"node="<<node2->value<<std::endl;
        node2 = node2->forward[2];
    }
    
    return 0;
}
